package com.buddy.summary.code.algorithm;

import java.util.Arrays;

//快速排序
public class QuickSort {


    //递归
    private static void quickSort(int[] arr, int startIndex, int endIndex) {
        //递归结束条件：startIndex >= endIndex
        if (startIndex > endIndex)
            return;
        //得到基准元素位置
//        int pivotIndex = partition1(arr,startIndex,endIndex);
        int pivotIndex = partition2(arr, startIndex, endIndex);
        //根据基准元素，分成两部分进行递归排序
        quickSort(arr, startIndex, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, endIndex);
    }

    //双边循环方法实现快速排序
    private static int partition1(int[] arr, int startIndex, int endIndex) {
        //选取第一个位置（也可以随机选取位置）
        int pivot = arr[startIndex];
        int left = startIndex;
        int right = endIndex;
        while (left != right) {
            while (left < right && arr[right] > pivot) {
                right--;
            }
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            //交换left和right指向的元素
            if (left < right) {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }
        //pivot和指针重合点交换
        arr[startIndex] = arr[left];
        arr[left] = pivot;
        return left;
    }

    //单边循环方法实现快速排序
    private static int partition2(int[] arr, int startIndex, int endIndex) {
        //取第一个位置作为基准元素
        int pivot = arr[startIndex];
        int mark = startIndex;
        for (int i = startIndex + 1; i <= endIndex; i++) {
            if (arr[i] < pivot){
                mark++;
                int temp = arr[mark];
                arr[mark] = arr[i];
                arr[i] = temp;
            }
        }
        arr[startIndex] = arr[mark];
        arr[mark] = pivot;
        return mark;
    }


    public static void main(String[] args) {
//        int[] arr1 = new int[]{4, 4, 6, 5, 3, 2, 8, 1};
//        quickSort(arr1, 0, arr1.length - 1);
//        System.out.println(Arrays.toString(arr1));
        int[] arr2 = new int[]{4,4,6,5,3,2,8,1};
        quickSort(arr2, 0, arr2.length - 1);
        System.out.println(Arrays.toString(arr2));

    }
}
